﻿// https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/
// 501. 二叉搜索树中的众数

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <limits.h>

using namespace std;

// struct ListNode {
//     int val;
//     ListNode *next;
//     ListNode() : val(0), next(nullptr) {}
//     ListNode(int x) : val(x), next(nullptr) {}
//     ListNode(int x, ListNode *next) : val(x), next(next) {}
// };

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        count = 0;
        maxCount = 0;
        TreeNode *pre = nullptr;
        result.clear();

        searchBST(root);
        return result;
    }
private:
    int maxCount; // 最⼤频率
    int count; // 统计频率
    TreeNode* pre;
    vector<int> result;
    void searchBST(TreeNode* cur) {
        if (cur == NULL) return ;
        searchBST(cur->left); // 左
        // 中
        if (pre == NULL) { // 第⼀个节点
            count = 1;
        } else if (pre->val == cur->val) { // 与前⼀个节点数值相同
            count++;
        } else { // 与前⼀个节点数值不同
            count = 1;
        }
        pre = cur; // 更新上⼀个节点
        if (count == maxCount) { // 如果和最⼤值相同，放进result中
            result.push_back(cur->val);
        }
        if (count > maxCount) { // 如果计数⼤于最⼤值频率
            maxCount = count; // 更新最⼤频率
            result.clear(); // 很关键的⼀步，不要忘记清空result，之前result⾥的元素都失效了
            result.push_back(cur->val);
        }
        searchBST(cur->right); // 右
        return ;
    }
};

int main() {
    Solution obj = Solution();
}